#include <bits/stdc++.h>
#define MAXN 100000
#define MAXM 10000

using namespace std;

const int maxN = 100005;
int N,M;
int wi[maxN],hi[maxN],t[maxN];

void attach(int i,int &w,int &h){
	if (w+wi[i] > M)
		h = max(h,(int)ceil(1.0*(M-w)*hi[i]/wi[i]));
	else
		h = max(h, hi[i]);
	w = min(M, w+wi[i]);
}

//从后往前计算，可以利用到之前的计算，因为隔一段时间一定会分行
int calc(int i,int w,int h){
	while(i < N && w < M)
		attach(i++,w,h);
	return h+t[i];
}

void solve(){
	int ans = INT_MAX,w,h,preSum;
	w = h = preSum = 0;
	for(int i = 0; i < N; ++i){
		int tmp = calc(i+1,w,h);
		ans = min(ans, preSum+tmp);
		attach(i,w,h);
		if(w == M){
			preSum += h;
			w = h = 0;
		}
	}
	printf("%d\n",ans);
}

int main()
{
    scanf("%d %d", &M, &N);
    //int photos[2][MAXN];
    for(int i = 0; i < N; i++){
        scanf("%d%d",&wi[i],&hi[i]);
        //scanf("%d %d", &photos[0][i], &photos[1][i]);
    }
    for(int i = N-1; i >= 0; --i)
            t[i] = calc(i,0,0);
    solve();
    /**O(N^2),数据过多超时
    int minHeight = INT_MAX;
    for(int i = 0; i < N; i++){
        int height = 0, wight = 0, lineheight = 0;
        for(int j = 0; j < N; j++){
            if(i == j)
                continue;
            if(wight < M){
                    if(M - wight >= photos[0][j]){
                        lineheight = lineheight > photos[1][j] ? lineheight : photos[1][j];
                        wight += photos[0][j];
                    }
                    else{
                        int tempwight = M - wight;
                        int temphight = ceil(photos[1][j] * tempwight / (float)photos[0][j]);
                        lineheight = lineheight > temphight ? lineheight :temphight;
                        wight += tempwight;
                    }
            }
            if(wight == M){
                height += lineheight;
                wight = 0;
                lineheight = 0;
            }
        }
        height += lineheight;
        minHeight = minHeight < height ? minHeight : height;
    }
    printf("%d\n", minHeight);
    */

    /**
    //O(MN)，此方法应该为O(mnn!),不可取
    int H[3][MAXN] = {0};//存储加入前i张图片后的总高度（不包括当前行高度）、当前行高度、当前行剩余宽度
    static int F[MAXM][2][MAXN] = {0};//存储当前行剩余宽度是j，这时开始加入第i张~最后一张后增加的高度（不包括当前行高度）、当前行高度
    int height = 0, wight = 0, lineheight = 0;
    for(int j = 0; j < N; j++)
    {
        if(wight < M)
        {
            if(M - wight >= photos[0][j])
            {
                lineheight = lineheight > photos[1][j] ? lineheight : photos[1][j];
                wight += photos[0][j];
            }
            else
            {
                int tempwight = M - wight;
                int temphight = ceil(photos[1][j] * tempwight / (float)photos[0][j]);
                lineheight = lineheight > temphight ? lineheight :temphight;
                wight += tempwight;
            }
        }
        H[0][j] = height + lineheight;
        H[1][j] = lineheight;
        H[2][j] = M - wight;
        if(wight == M)
        {
            height += lineheight;
            wight = 0;
            lineheight = 0;
        }
    }
    for(int i = 0; i < M; i++)
    {
        for(int k = 0; k < N; k++){
        height = 0;
        wight = i;
        lineheight = 0;
        bool flag = true;//标记当前行结束
        for(int j = k; j < N; j++)
        {
            if(wight < M)
            {
                if(M - wight >= photos[0][j])
                {
                    lineheight = lineheight > photos[1][j] ? lineheight : photos[1][j];
                    wight += photos[0][j];
                }
                else
                {
                    int tempwight = M - wight;
                    int temphight = ceil(photos[1][j] * tempwight / (float)photos[0][j]);
                    lineheight = lineheight > temphight ? lineheight :temphight;
                    wight += tempwight;
                }
            }
            if(wight == M)
            {
                if(flag){
                    flag = false;
                    F[i][1][k] = lineheight;
                }
                else
                    height += lineheight;
                wight = 0;
                lineheight = 0;
            }
        }
        F[i][0][k] = height;
        }
    }
    int minH = INT_MAX, tempheight = 0;
    //删除第一个图片后高度
    tempheight = F[0][0][1] + F[0][1][1];
    minH = minH < tempheight ? minH : tempheight;
    //删除最后一个图片后的高度
    tempheight = H[0][N-2] + H[1][N-2];
    minH = minH < tempheight ? minH : tempheight;
    //删除第2——N-1个图片后的高度
    for(int i = 1; i < N - 1; i++){
        tempheight = H[0][i-1] + F[H[2][i-1]][0][i+1] + max(H[1][i-1], F[H[2][i-1]][1][i+1]);
        minH = minH < tempheight ? minH : tempheight;
    }
    printf("%d\n", minH);
    */

    return 0;
}

/**

题目1 : 图片排版
时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Ho需要在一篇文档中加入N张图片，其中第i张图片的宽度是Wi，高度是Hi。

假设纸张的宽度是M，小Ho使用的文档编辑工具会用以下方式对图片进行自动排版：

1. 该工具会按照图片顺序，在宽度M以内，将尽可能多的图片排在一行。该行的高度是行内最高的图片的高度。例如在M=10的纸张上依次打印3x4, 2x2, 3x3 三张图片，则效果如下图所示，第一行高度为4。(分割线以下为排版区域；数字x组成的矩形为第x张图片占用的版面。)

0123456789
----------
111
111  333
11122333
11122333

2. 如果当前行剩余宽度大于0，并且小于下一张图片，则下一张图片会按比例缩放到宽度为当前行剩余宽度(高度向上取整)，然后放入当前行。例如再放入一张4x9的图片，由于剩余宽度是2，这张图片会被压缩到2x5，再被放入第一行的末尾。此时第一行高度为5：

0123456789
----------
        44
111     44
111  33344
1112233344
1112233344

3. 如果当前行剩余宽度为0，该工具会从下一行开始继续对剩余的图片进行排版，直到所有图片都处理完毕。此时所有行的总高度就是这N张图片的排版高度。例如再放入11x1, 5x5, 3x4的图片后，效果如下图所示，总高度为11：

0123456789
----------
        44
111     44
111  33344
1112233344
1112233344
5555555555
66666
66666777
66666777
66666777
66666777

现在由于排版高度过高，图片的先后顺序也不能改变，小Ho只好从N张图片中选择一张删除掉以降低总高度。他希望剩余N-1张图片按原顺序的排版高度最低，你能求出最低高度是多少么？
输入

第一行包含两个整数M和N，分别表示纸张宽度和图片的数量。

接下来N行，每行2个整数Wi, Hi，表示第i个表情大小为Wi*Hi。

对于30%的数据，满足1<=N<=1000

对于100%的数据，满足1<=N<=100000，1<=M, Wi, Hi<=100
输出

输出在删除掉某一张图片之后，排版高度最少能是多少。
样例输入

    4 3
    2 2
    2 3
    2 2

样例输出

    2

*/

/**

《图片排版》题目分析

本题显而易见的做法是直接枚举删除了哪张图片，复杂度O(N)；然后再通过O(N)的模拟排版计算出最后的高度。总的时间复杂度是O(N^2)。

优化的方法是用空间换时间，先预处理出一些有用的数据。

H(i)：从头开始加入前i张图片后的情况，记录总高度、当前行高度、当前行剩余宽度。计算所有H(i)的复杂度是O(N)。

F(i, j)： 假设当前行剩余宽度是j，这时开始加入第i张~最后一张的情况，记录增加的高度、当前行高度。计算所有F(i, j)的复杂度是O(NM)。

有了H(i)和F(i, j)，我们再枚举删除的图片时，就可以直接合并相应的H和F，得到最终的高度。注意合并时，当前行高度需要取H和F两者中较大的。

总的复杂度是O(NM)。

*/
